BZOJ3165【HEOI2013】Segment <李超线段树>

Problem

【HEOI2013】Segment

Description

要求在平面直角坐标系下维护两个操作：

在平面上加入一条线段。记第条被插入的线段的标号为。
给定一个数，询问与直线相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数，表示共个操作。
接下来行，每行第一个数为或。
若该数为，则后面跟着一个正整数，表示询问与直线相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为，则后面跟着四个正整数，表示插入一条两个端点为,和,的线段。
其中为上一次询问的答案。初始时。

Output

对于每个操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。
若不存在与直线相交的线段，答案为。

Sample Input

Sample Output

1
2

2 
0 3

HINT

对于的数据，, , 。

标签：李超线段树

Solution

李超线段树模板题。

用线段树维护线段。对于每个区间，维护这个区间的“优选线段”，即对于多数值是最优的线段。
插入一条线段时，首先判断是否完全优于或完全劣于当前区间的优选线段。如果完全更优就覆盖后返回，如果完全更劣就直接返回。这样只剩下部分优于当前区间优先线段的情况。计算出两线段交点，令两线段中取最优值的部分较多的那条为，较少的那条为。如果交点在左区间，那么一定不可能是右区间的最优线段，否则取最优值的部分比多，与定义矛盾。于是将作为本区间的优选线段，然后递归试图将插入左区间中。同样地，交点在右区间时，将递归插入右区间即可。
查询一个值时，将线段树从根到值为的叶子结点的路径上的所有线段在处的取值取最大值即可。
总复杂度。

Code

#include <bits/stdc++.h>
#define R 40000
#define P1 39989
#define P2 1000000000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct line {int id; dnt k, b;} tr[R<<2];
dnt calc(line l, int x) {return l.k*x+l.b;}
line max(line a, line b, int x) {
    dnt val1 = calc(a, x), val2 = calc(b, x);
    if (val1 == val2) return a.id < b.id ? a : b;
    return val1 > val2 ? a : b;
}
void insert(int v, int s, int t, line L) {
    if (!tr[v].id) {tr[v] = L; return;}
    line a = tr[v], b = L;
    dnt sa = calc(a, s), sb = calc(b, s);
    dnt ta = calc(a, t), tb = calc(b, t);
    if (sa >= sb && ta >= tb) {tr[v] = a; return;}
    if (sa <= sb && ta <= tb) {tr[v] = b; return;}
    dnt p = (a.b-b.b)/(b.k-a.k);
    if (sa > sb) {
        if (p <= (dnt)mid) insert(v<<1, s, mid, a), tr[v] = b;
        if (p > (dnt)mid) insert(v<<1|1, mid+1, t, b),tr[v] = a;
    } else {
        if (p <= (dnt)mid) insert(v<<1, s, mid, b), tr[v] = a;
        if (p > (dnt)mid) insert(v<<1|1, mid+1, t, a), tr[v] = b;
    }
}
void modify(int v, int s, int t, int l, int r, line L) {
    if (s >= l && t <= r) {insert(v, s, t, L); return;}
    if (l <= mid) modify(v<<1, s, mid, l, r, L);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, L);
}
line query(int v, int s, int t, int x) {
    if (s == t) return tr[v]; line ret;
    if (x <= mid) ret = query(v<<1, s, mid, x);
    if (x >= mid+1) ret = query(v<<1|1, mid+1, t, x);
    return max(tr[v], ret, x);
}
int main() {
    int T, n = 0; read(T), tr[0].b = (dnt)-INF;
    for (int lst = 0; T; T--) {
        int opt; read(opt);
        if (opt == 0) {
            int x; read(x), x = (x+lst-1)%P1+1;
            line res = query(1, 1, R, x);
            printf("%d\n", lst = res.id);
        }
        if (opt == 1) {
            int x0, y0, x1, y1; dnt k, b;
            read(x0), x0 = (x0+lst-1)%P1+1;
            read(y0), y0 = (y0+lst-1)%P2+1;
            read(x1), x1 = (x1+lst-1)%P1+1;
            read(y1), y1 = (y1+lst-1)%P2+1;
            if (x0 > x1) swap(x0, x1), swap(y0, y1);
            if (x0 == x1) k = 0, b = max(y0, y1);
            else k = 1.0*(y0-y1)/(x0-x1), b = y0-k*x0;
            modify(1, 1, R, x0, x1, (line){++n, k, b});
        }
    }
    return 0;
}